1. Field of the Invention
The present invention relates to an encoding method, an encoding apparatus, a decoding method, a decoding apparatus, and a recording medium. More particularly, the present invention relates to an encoding method, an encoding apparatus, a decoding method, a decoding apparatus, and a recording medium, which are suitable for recording various types of data such as video data, audio data, and other digital data on a recording medium such as a magnetic disk, magnetic tape, optical disk, magneto-optical disk, and phase-change disk.
2. Description of the Related Art
When video data or audio data is recorded in a digital fashion on a disk such as a magnetic disk or an optical disk, or a magnetic tape so that it can be reproduced later, it is desirable that the data can be recorded with high density. To meet the above requirement, digital data is recorded, in many cases, by means of partial response (1, 0, -1) or partial response (1, 1). The partial response (1, 0,-1) or partial response (1, 1) technique may be combined with the maximum likelihood decoding (detection) technique so as to realize higher-density recording. This mixed technique is referred to as the partial response maximum likelihood (PRML) technique. Maximum likelihood decoding is generally realized using the Viterbi decoding (detection) technique.
In the mixed technique of PRML, if encoding is performed in such a manner as to have a large free squared Euclidean distance (hereinafter also referred to simply as a free distance), the signal-to-noise ratio can be improved and thus it becomes possible to achieve high-density recording. This technique is called the trellis coded partial response (TCPR) scheme. A code generated according to this coding method is one of trellis codes.
The free distance refers to a minimum Euclidean distance between two different paths which emerge from the same state and which end at the same state in a trellis diagram representing an output sequence of a partial-response channel (such a trellis is referred to as a detection trellis, and Viterbi detection may be performed based on a detection trellis). The starting state and the ending state may or may not be identical to each other.
For example, in the partial response (1, 0, -1) scheme (hereinafter referred to simply as the PR4 scheme), when the free distance detected by the conventional bit-by-bit detection technique is 1, a free distance of 2 can be obtained in the Viterbi detection. Since the signal-to-noise ratio increases with the free distance, the recording density increases with the free distance. Furthermore, in conjunction with the PR4 scheme, a practical technique is known to obtain a trellis code having a free distance even greater than 4.
In theory, it is possible to increase the free distance if the power spectrum of a code has a null coincident with the null of the transfer function of a communication line. Trellis codes generated according to this theory are called matched spectral null (MSN) codes.
For example, in the PR4 scheme, the free distance can be increased by generating a code in such a manner that its power spectrum has a null at a DC frequency and also at a frequency (Nyquist frequency) equal to one-half the recording rate (=1/Tc where Tc is the time period (bit period) of each code bit).
On the other hand, in the partial response (1, 1) scheme (hereinafter referred to as the PR1 scheme), a large free distance can be obtained when the power spectrum of a code has a null at the Nyquist frequency.
If +1 and -1 are assigned to code symbols "1" and "0", respectively, and if the sum of assigned values for a code sequence calculated from its start (starting point), then the sum can be used as a measure for indicating the DC component of the power spectrum of the code. This sum is called the RDS (running digital sum) of the code sequence. If the RDS falls within a certain range, the DC component of the power spectrum of the code can be considered to be null.
An alternating digital sum (ADS) can be defined as the value which is obtained by first multiplying -1 with every two elements of a sequence of codes which are assigned alternately +1 and -1 as with the calculation of the RDS, and then calculating the sum of the values of all elements of the resultant sequence. The ADS can be used as a measure for evaluating the Nyquist frequency component. That is, if the ADS falls within a particular range, the power spectrum of the code can be regarded as having a null at its Nyquist frequency.
When the transfer function has a DC component as with the case in a PR1 system, it is generally required that the DC component of power spectrum of the code should be null. For example, in a magnetic recording/reproducing system having a derivative characteristic in its reproducing section, it is required that codes to be recorded include no DC component, because a DC component can cause a fluctuation of the reference level during the operation of detecting codes from a playback signal by means of Viterbi detection, and thus an error can occur due to such a fluctuation. The above requirement should also be met to prevent a fluctuation from occurring in various error signals such as a tracking error signal used in servo control for a disk drive for recording or reproducing data on or from an optical disk or a magneto-optic disk.
To achieve the above requirement, in many modulation/conversion techniques such as the 8/10 conversion coding used in a digital audio tape recorder (DAT), eight-to-fourteen modulation (EFM) used in a compact disk (CD) player, and the Miller square (Miller-2) scheme used in a magnetic disk drive, the digital sum variation (DSV) or the variation in the RDS of an not return to zero (NRZ) code in which modulation occurs as to mark position or of an no return to zero inverted (NRZI) code in which modulation occurs as to mark length is controlled to a low level.
Furthermore, when the PRML technique is employed, the length of a path memory used in Viterbi detection is an important consideration. The path memory is used to store a temporary result during a Viterbi detection process until a final result is obtained. Therefore, the path memory is required to have a length (storage capacity) corresponding to the period of time required to obtain the final detection result (decoding result).
The period of time required to obtain final Viterbi detection result, which determines the required length of the path memory, can be controlled by generating codes such that no quasi-catastrophic sequences occur.
The quasi-catastrophic sequences refer to two or more paths in a trellis diagram, which occur infinitely for a particular code bit sequence. For example, when a code sequence 101010 is given, if transitions such as 111 . . . 333 . . . , and 555 . . . , occur infinitely on a trellis diagram, these three paths are called quasi-catastrophic sequences. Quasi-catastrophic sequences run along parallel paths in a trellis diagram. The squared Euclidean distances among those paths are never accumulated and are maintained at zero. Therefore, it is impossible to determine which sequence of those sequences is correct. In other words, it is impossible to select a correct path. Thus, if quasi-catastrophic sequences occur, it becomes impossible to obtain a unique result in Viterbi detection.
When a practical apparatus for performing Viterbi detection is produced, it is impossible to produce a path memory having an infinite length. On the contrary, it is needed to reduce the length of the path memory as possible so as to meet requirements of low cost and small installation space. For the above reasons, it is required to eliminate quasi-catastrophic sequences for example as follows.
In the case where 8/10 coding is performed using the PRI technique, quasi-catastrophic sequences can be prevented by limiting the number of successive is in a data sequence to be subjected to NRZI process.
In record signals or codes, Tmin (the minimum length of a succession of identical symbols) and Tmax (the maximum length of a succession of identical symbols) are both important measures for evaluating the performance of the codes.
It is desirable that Tmax be as small as possible. For example, in a magnetic recording/reproducing apparatus, great Tmax can cause degradation in erasing ratio during an overwrite operation. On the other hand, in azimuth recording, large Tmax can increase cross talk from an adjacent track, which results in degradation of quality of reproduced data. Furthermore, in a phase locked loop (PLL) operation, large Tmax can cause a loss of information used for synchronization, which causes an error in operation.
An MSN code called partitioned-MSN 8/10-rate code which can have a free distance of 4 when coupled with the PR4 technique has been recently proposed by L. Fredrickson, R. Karabed, J. Rae, P. Siegel, H. Thapar and R. Wood ("Improved Trellis-coding for Partial-Response Channels", IEEE Transactions on Magnetics, Vol. 31, No. 2, March 1995). This technique can generate a code with a path memory length shorter than required in known 8/10-rate MSN codes (for example an MSN code disclosed in U.S. Pat. No. 5,095,484 or such that proposed by H. Thapar, J. Rac, C. Shung, R. Karabed and P. Siegel (On the performance of a Rate 8/10 Matched Spectral Null Code for Class-4 Partial Response", IEEE Transactions on Magnetics, Vol. 28, No. 5, September, 1992).
FIG. 32 illustrates a rule of generating an 8/10-rate partitioned-MSN code.
In FIG. 32, there is shown a trellis representing changes in RDS of a code (partitioned-MSN code) generated in response to transitions of states (hereinafter such a trellis will be referred to as an RDS trellis). In this RDS trellis, whenever a state transition occurs after starting from the start point, a 1-bit code is output (generated), and thus, a 10-bit code is generated when arriving at the end point. Therefore, the 0th bit of the code corresponds to the start point and the 10th bit corresponds to the end point.
In the example shown in FIG. 32, the RDS at the start point of the RDS trellis has a value of 3 or 5.
In the case where the RDS is equal to 3 at the start point, +1 or +3 is added to the RDS during a path to the 5th bit, and thus the RDS becomes 4 or 6. On the other hand, when the RDS is equal to 5 at the start point, -1 or 3 is added to the RDS during a path to the 5th bit, and thus the RDS becomes 4 or 2. In any case, the RDS returns to 3 or 5 at the 10th bit or the end point.
Those points other than the start and end points where the RDS is limited to particular values are referred to as linked points. In the specific example shown in FIG. 32, the RDS at the 5th bit is limited to 2, 4, or 6, and thus the 5th bit is a linked point.
In FIG. 32, when the RDS has a value of 3 at the start point, the RDS is inhibited from having a particular value (2 in this example) at the 5th bit (the linked point), of those values of 2, 4, and 6. In the case where the RDS has a value of 5 at the start point, on the other hand, the RDS is inhibited from having a particular value (6 in this example) at the 5th bit (the linked point), of those values of 2, 4, and 6. In partitioned-MSN coding, as described above, the RDS is inhibited from having a particular value at a linked point depending on what value the RDS has at the start point. This prevents the detection trellis from having parallel paths within a 10-bit length, thus preventing quasi-catastrophic sequences from occurring. As a result, it becomes possible to reduce the length of the path memory.
When partitioned-MSN code are generated using the PR4 technique, two codes may be interleaved in such a manner that the power spectrum of the resultant interleaved code has a null at both DC frequency and Nyquist frequency. Since Tmax associated with uninterleaved 10-bit codes obtained by the process described above with reference to FIG. 32 is equal to 6Tc, Tmax for interleaved codes becomes equal to 12Tc (=2.times.6Tc).
The partial response characteristic can be represented by a transfer polynomial expression. If a delay operator representing a delay in time Tc (a bit-period delay operator) is denoted by D, then for example PR4 can be represented as (1-D)2, and PR1 can be represented as (1+D). The expression (1-D)2 can be divided into two expressions each comprising (1-D). Therefore, in PR4, if a code is sampled at time intervals of 2Tc and is divided into two sequences, then each sequence can be represented by (1-D). In the case of PR4, therefore, Viterbi detection is generally performed independently for a sequence of values sampled at times of Tc.times.2n and for a sequence of values sampled at times of Tc.times.(2n+1). This process is thus equivalent to the process of separately detecting two uninterleaved codes.
FIG. 33 illustrates an example of a detection trellis corresponding to (1-D). The code generation rule shown in FIG. 32 is directly reflected in this detection trellis. Therefore, the mechanism for preventing quasi-catastrophic sequences from occurring is also realized in this detection trellis. That is, in the section from the start point to a linked point (the 5th bit in this example), the detection trellis is divided into two parts depending on whether the RDS is 3 or 5 in the initial state. This trellis structure prevents quasi-catastrophic sequences from occurring.
FIG. 34 illustrates another example of a detection trellis corresponding to (1-D). In this example, unlike the example shown in FIG. 33, the detection trellis is not divided into a plurality of parts, and the same detection trellis is used regardless of the RDS value at the start point. In this case, when a code is generated, no restriction is imposed on the RDS value regardless of its value at the start point. In other words, there is a possibility that paths. (for example, shaded paths in FIG. 34) which result in quasi-catastrophic sequences are taken in Viterbi detection process. In this case, the generalized truncation depth (GTD), which is a measure of the length required for the pass memory, becomes 20 bits.
Herein, the GTD refers to a maximum path length of all possible pairs of paths which emerge from their common states and which run until the squared Euclidean distance between possible pairs of paths reaches a predetermined value (for example 4 in the case of the partitioned MSN code). Herein, one of each pair of paths is assumed to be generated by a code.
To achieve desired performance, it is required that the length of the path memory should be at least equal to or greater than GTD.
If PR1 and PR4 are compared to each other, the spectrum with PRl includes lower high-frequency components and thus includes less high-frequency noise. Therefore, PR1 is more suitable for use in high linear density recording. Therefore, it is desirable to apply the above-described trellis code to PR1 to achieve high linear density.
FIG. 35 illustrates the relationship between the error rate and the linear density for PR1 and PR4, reported in a paper titled "8/10 PR1ML for High Density and High Rate Tape Storage Systems" (IEEE Transaction on Magnetics, Vol. 31, No. 6, November, 1995, pp. 3036-3038). In FIG. 35, the horizontal axis represents the linear density in Kbpi, which indicates how many bits are recorded per inch in a linear direction, wherein a greater value indicates a higher linear density. As can be seen from FIG. 35, PR1 (8/10 PR1ML) provides a better (lower) error rate than PR4 (8/9 PR4ML) in the high linear density range.
The inventors of the present invention have proposed a technique of generating a 16/20 trellis code with a high conversion efficiency (coding efficiency) for PR1 in Japanese Patent Publication No. 8-64143. This technique can provide a coding efficiency of 4/5 which is the same as that obtained by the 8/10 coding technique. Therefore, the power spectrum of 16/20 codes has a null at the Nyquist frequency and it includes no DC component. Therefore, the desirable DSV control can be achieved and the free distance can be equal to 4. The GTD is 5 times the code length (=100 bits=5.times.20 bits), and Tmax=10Tc.
In the 16/20 codes, since the GTD is equal to 100 bits, the required length of the path memory is also of the order of 100 bits. However, it is desirable to further reduce the length of the path memory so as to reduce the hardware size and production cost. In this technique proposed by the inventors of the present invention, since data with a rather long length such as 16 bits is encoded into 20-bit data, and 20-bit data is decoded into 16-bit data, large-sized encoding and decoding apparatus are required.
That is, to perform encoding/decoding between m-bit and n-bit data, the memory in the encoder should have a capacity greater than 2 m.times.n bits and the memory in the decoder should have a capacity greater than 2 n.times.m bits. This means that if m and n are reduced, the memory capacity required by the encoder/decoder decreases exponentially. This allows a great reduction in the hardware size. For the above reason, it is desirable that the unit length m of data to be converted to codes and the unit length n of codes should be as small as possible.
A sequence of interleaved partitioned-MSN codes generated according to the scheme shown in FIG. 32 may be applied not only to PR4 but also to PR1, because the power spectrum of the sequence of interleaved codes has a null at the Nyquist frequency and includes no DC component, and because no quasi-catastrophic sequences occur when it is applied to PR1. Since the power spectrum includes no DC component, the above-described problems caused by the DC component do not occur. Furthermore, since the Nyquist-frequency component of the power spectrum is null, it is possible to achieve a free distance of 4 for PR1. When a partitioned-MSN code is used with PR1, the GTD becomes 40 bits which is fairly smaller than the GTD of 100 bits associated with the 16/20 codes described above.
However, when the partitioned MSN code is applied to PR1 in such a manner as shown in FIG. 32, if a detection trellis which is divided into sub-trellises according to the initial state as shown in FIG. 33 is employed in the decoding operation, the detection trellis corresponding to interleaved codes can include invalid state transitions which cannot be generated by any code as will be described in detail later. Therefore, it is impossible to eliminate all quasi-catastrophic sequences.
If a detection trellis is divided into a plurality of parts as in FIG. 33, the total number of states becomes greater than that of the original detection trellis. In both detection trellises shown in FIGS. 33 and 34 (and also in the RDS trellis shown in FIG. 32, and in those RDS trellises, detection trellises and ADS trellises which will be described later), the vertical axis represents possible states which change along the horizontal axis. In the case of the undivided detection trellis shown in FIG. 34, the maximum possible number of states is 6 which occurs at 2nd to 9th bits. In contrast, in the divided detection trellis shown in FIG. 33, the maximum number of states is 10 which occurs at the 3rd and 4th bits. Taking into account the fact that the hardware size of a Viterbi detector increases with the number of states, it is desirable to employ an undivided detection trellis.
When two partitioned-MSN codes described above with reference to FIG. 32 are interleaved into a single code, Tmax associated with the resultant interleaved code becomes 12Tc as described above. However, Tmax associated with 8/10 codes used in DATs or DDSs is equal to 4Tc, which is fairly smaller than the above value. As described earlier, it is desirable that Tmax should be as small as possible.
In addition to the partitioned MSN code described above with reference to FIG. 32, some techniques of generating similar 8/10-rate MSN codes are known. The power spectrum of these codes includes no DC component and has a null at the Nyquist frequency. If only this fact is considered, these codes seem capable of being applied to PR1. In reality, however, these MSN codes employ different techniques to reduce the length of the path memory, and thus these MSN codes are difficult to be applied to PR1.
In view of the above, it is an object of the present invention to provide a technique of generating a partitioned-MSN code which is small in Tmax and which can be applied not only to PR1 but also to partial response represented by a transfer polynomial of (1+D)n. It is another object of the present invention to provide a technique of effectively removing quasi-catastrophic sequences without dividing a detection trellis thereby reducing the number of states in the detection trellis whereby the length of a path memory is reduced, thus achieving a Viterbi detector with a reduced size. It is a further object of the present invention to provide a technique of constructing a small-sized encoder/decoder for encoding/decoding a partitioned MSN code.